package com.kx.demo.jdk.collection;

import java.util.HashMap;

/**
 * 自定义LRU
 *
 * @author kx
 * @date 2020/4/12
 */
public class LRUCustom<K, V> {

    private Node<K, V> first = null;
    private Node<K, V> last = null;
    private HashMap<K, Node<K, V>> map;
    private final int maxCapacity;

    public LRUCustom(int maxCapacity) {
        this.maxCapacity = maxCapacity;
        map = new HashMap<>();
    }

    /**
     * 获取元素
     *
     * @param key key
     * @return 值
     */
    public V get(K key) {
        if (!map.containsKey(key)) {
            return null;
        }
        Node<K, V> node = map.get(key);
        moveToTail(node);
        return node.value;
    }

    /**
     * 添加键值
     *
     * @param key   键
     * @param value 值
     */
    public void put(K key, V value) {
        if (map.containsKey(key)) {
            Node<K, V> oldNode = map.get(key);
            moveToTail(oldNode);
        } else {
            Node<K, V> node = new Node<>(key, value);
            addToTail(node);
            map.put(key, node);
        }
    }

    /**
     * 删除值
     *
     * @param key key
     * @return 删除的值
     */
    public V remove(K key) {
        if (!map.containsKey(key)) {
            return null;
        }
        Node<K, V> node = map.remove(key);
        removeFromNode(node);
        return node.value;
    }

    /**
     * 将节点移到链表前端
     *
     * @param node 节点
     */
    private void addToTail(Node<K, V> node) {
        if (map.size() >= maxCapacity) {
            removeHead();
        }
        Node<K, V> l = last;
        last = node;
        if (l == null) {
            first = node;
        } else {
            l.next = node;
            node.prev = l;
        }
    }

    /**
     * 删除头结点
     */
    private void removeHead() {
        if (first == null) {
            return;
        }
        // 解除节点关联
        Node<K, V> f = first;
        first = f.next;
        f.next = null;
        first.prev = null;

        // 删除map对应对象
        map.remove(f.key);
    }

    /**
     * 在链表中删除节点
     *
     * @param node 节点
     */
    private void removeFromNode(Node<K, V> node) {
        Node<K, V> prev = node.prev;
        Node<K, V> next = node.next;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            node.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            node.next = null;
        }

    }

    /**
     * 将元素移动到队尾
     *
     * @param node 节点
     */
    private void moveToTail(Node<K, V> node) {
        if (node == last || last == null) {
            return;
        }

        Node<K, V> l = last;
        Node<K, V> prev = node.prev;
        Node<K, V> next = node.next;
        last = node;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            node.prev = null;
        }

        if (next == null) {
            // 保持一致
            last = node;
        } else {
            next.prev = prev;
            node.next = null;
        }

        l.next = node;
        node.prev = l;
    }

    /**
     * 双向链表节点数据结构
     *
     * @param <K> key
     * @param <V> value
     */
    static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev = null;
        Node<K, V> next = null;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * 重写 toString 方法
     *
     * @return 字符串对象
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LRUCustom[");
        Node<K, V> f = first;
        while (f != null && f.next != null) {
            sb.append(f.key).append("=").append(f.value).append(", ");
            f = f.next;
        }
        if (last != null) {
            sb.append(last.key).append("=").append(last.value);
        }
        sb.append("]");
        return sb.toString();
    }

    public static void main(String[] args) {
        LRUCustom<Integer, Integer> lruCustom = new LRUCustom<>(4);
        System.out.println(lruCustom);
        lruCustom.put(1, 1111);
        lruCustom.put(2, 222);
        lruCustom.put(4, 4444);
        lruCustom.put(5, 555);
        lruCustom.put(6, 6666);
//        System.out.println(lruCustom.get(2));
        lruCustom.put(3, 333);
        lruCustom.get(4);
        lruCustom.get(2);
        System.out.println(lruCustom);
        System.out.println(lruCustom.remove(5));
        lruCustom.get(3);
        System.out.println(lruCustom);
    }
}
